// https://www.lintcode.com/problem/triangle/

public class Solution {
    /**
     * @param triangle: a list of lists of integers
     * @return: An integer, minimum path sum
     */
    public int minimumTotal(int[][] triangle) {
        // write your code here
        int i = 1;
        List<Integer> dists = new ArrayList<>();
        dists.add(triangle[0][0]);
        while (i < triangle.length) {
            List<Integer> newDists = new ArrayList<>();
            newDists.add(triangle[i][0] + dists.get(0));
            for (int j = 1; j < triangle[i].length; ++j) {
                if (j == (triangle[i].length - 1)) {
                    newDists.add(triangle[i][i] + dists.get(dists.size() - 1));
                } else {
                    newDists.add(triangle[i][j] + Math.min(dists.get(j - 1), dists.get(j)));
                }
            }
            dists.clear();
            dists.addAll(newDists);
            ++i;
        }
        int ret = dists.get(0);
        for (int j = 1; j < dists.size(); ++j) {
            if (dists.get(j) < ret) {
                ret = dists.get(j);
            }
        }
        return ret;
    }
}